package com.gxc.tree;

/**
 * 给定一棵二叉树的头节点head，可以从树中的任何一点出发，如果走的话只能向下也可以选择随时停止，
 * 所形成的轨迹叫做一条路径，路径上所有值的累加和叫作路径和。
 * 求这棵树上的最大路径和。
 */
public class MaximumPathSum {

    public static void main(String[] args) {

    }

    public int process(TreeBean head) {
        return recursion(head).maxSum;
    }

    public Info recursion(TreeBean node) {
        if (node == null) return new Info(0, 0);

        Info left = recursion(node.left);
        Info right = recursion(node.right);

        int leftSum = left.sum>0?left.sum:0;
        int rightSum = right.sum>0?right.sum:0;
        int childMax = Math.max(leftSum, rightSum);
        int max = Math.max(left.maxSum, right.maxSum);

        return new Info(node.value + childMax, Math.max(node.value + childMax, max));
    }

    public class Info {

        //当前节点的路径和
        public int sum;
        //当前节点包含子节点达到过的最大路径和
        public int maxSum;

        public Info(int sum, int maxSum) {
            this.sum = sum;
            this.maxSum = maxSum;
        }
    }
}
